Having derived the guaranteed $O(n \log n)$ time complexity for Merge Sort, we now turn our attention to its other crucial properties: stability and space usage.
- Time Complexity Guarantee: Merge Sort’s performance is entirely predictable. Since the Divide and Conquer structure always ensures $\log n$ levels of recursion and the Merge step always performs $O(n)$ work, its time complexity remains $O(n \log n)$ in the best, average, and worst cases.
- Stability: Merge Sort is an inherently stable sorting algorithm. This means that if two elements have equal keys, their relative order in the input array $A$ is preserved in the output array $B$.
- Auxiliary Space: The primary drawback of Merge Sort is its space requirement. It is an out-of-place algorithm because the merge step requires a temporary auxiliary array. This mandates $O(n)$ auxiliary space, which can be prohibitive in memory-constrained environments.
| Property | Best Case | Average Case | Worst Case | Auxiliary Space | Stable? |
|---|---|---|---|---|---|
| Merge Sort | $O(n \log n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(n)$ | Yes |